Product Code Database
In the context of combinatorial game theory, a game tree is a graph representing all possible game states within a sequential game that has perfect information. Such games include chess, Draughts, Go, and tic-tac-toe.
A game tree can be used to measure the Game complexity, as it represents all the possible ways that the game can pan out. Due to the large game trees of complex games such as chess, algorithms that are designed to play this class of games will use partial game trees, which makes computation feasible on modern computers. Various methods exist to solve game trees. If a complete game tree can be generated, a deterministic algorithm, such as backward induction or retrograde analysis can be used. Randomized algorithms and minmax algorithms such as MCTS can be used in cases where a complete game tree is not feasible.
The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position; the complete tree is the same tree as that obtained from the extensive-form game representation. To be more specific, the complete game is a norm for the game in game theory. Which can clearly express many important aspects. For example, the sequence of actions that stakeholders may take, their choices at each decision point, information about actions taken by other stakeholders when each stakeholder makes a decision, and the benefits of all possible game results.
The number of in the complete game tree is the number of possible different ways the game can be played. For example, the game tree for tic-tac-toe has 255,168 leaf nodes.
Game trees are important in artificial intelligence because one way to pick the best move in a game is to search the game tree using any of numerous tree search algorithms, combined with minimax-like rules to prune the tree. The game tree for tic-tac-toe is easily searchable, but the complete game trees for larger games like chess are much too large to search. Instead, a chess-playing program searches a partial game tree: typically as many plies from the current position as it can search in the time available. Except for the case of "pathological" game trees (which seem to be quite rare in practice), increasing the search depth (i.e., the number of plies searched) generally improves the chance of picking the best move.
Two-person games can also be represented as . For the first player to win a game, there must exist a winning move for all moves of the second player. This is represented in the and-or tree by using disjunction to represent the first player's alternative moves and using conjunction to represent all of the second player's moves.
The diagram shows a game tree for an arbitrary game, colored using the above algorithm.
It is usually possible to solve a game (in this technical sense of "solve") using only a subset of the game tree, since in many games a move need not be analyzed if there is another move that is better for the same player (for example alpha-beta pruning can be used in many deterministic games).
Any subtree that can be used to solve the game is known as a decision tree, and the sizes of decision trees of various shapes are used as measures of game complexity.Victor Allis (1994). 9789090074887, Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands. . ISBN 9789090074887
The following is an implementation of randomized game tree solution algorithm:
"""Returns True if this node evaluates to a win, otherwise False"""
if u.leaf:
return u.win
else:
random_children = (gt_eval_rand(child) for child in random_order(u.children))
if u.op == "OR":
return any(random_children)
if u.op == "AND":
return all(random_children)
The algorithm makes use of the idea of "short-circuiting": if the root node is considered an "" operator, then once one is found, the root is classified as ; conversely, if the root node is considered an "" operator then once one is found, the root is classified as .
|
|
